This invention is in the field of data communications, and is more specifically directed to redundant coding for error detection and correction in such communications.
High-speed data communication services, for example in providing high-speed Internet access, have become a widespread utility for many businesses, schools, and homes. In its current stage of development, this access is provided by an array of technologies. Some data communication approaches use existing telephone lines, with relatively slow data rates provided by voice band modems (e.g., according to the current v.92 communications standards), and higher data rates provided by Digital Subscriber Line (DSL) technology. Another current technology involves the use of cable modems communicating over coaxial cable, often in combination with cable television services. The Integrated Services Digital Network (ISDN) is a system of digital phone connections over which data is transmitted simultaneously across the world using end-to-end digital connectivity. Localized wireless network connectivity according to the IEEE 802.11 standard has become popular for connecting computer workstations and portable computers to a local area network (LAN), and typically through the LAN to the Internet. Broadband wireless data communication technologies, for example those technologies referred to as “WiMAX” and “WiBro”, and those technologies according to the IEEE 802.16d/e standards, are now being developed to provide wireless DSL-like connectivity in the Metro Area Network (MAN) and Wide Area Network (WAN) context.
A problem that is common to all data communications technologies is the corruption of data by noise. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol as received differs from the data bit or symbol as transmitted. This likelihood of a data error is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.
Error detection and correction techniques are typically implemented by the technique of redundant coding. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate, on decoding, whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream even if errors are present.
Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example repeating the payload twice, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood exists that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.
The well-known Shannon limit provides a theoretical bound on the optimization of decoder error as a function of data rate. The Shannon limit provides a metric against which codes can be compared, both in the absolute and relative to one another. Since the time of the Shannon proof, modern data correction codes have been developed to more closely approach the theoretical limit. An important class of these conventional codes includes “turbo” codes, which encode the data stream by applying two convolutional encoders. One of these convolutional encoders encodes the datastream as given, while the other encodes a pseudo-randomly interleaved version of the data stream. The results from the two encoders are interwoven to produce the encoded data stream.
Another class of known redundant codes are the Low Density Parity Check (LDPC) codes. The fundamental paper describing these codes is Gallager, Low-Density Parity-Check Codes, (MIT Press, 1963), monograph available at http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/. In these codes, a sparse matrix H defines the code, with the encodings c of the payload data satisfying:Hc=0  (1)over Galois field GF(2). Each encoding c consists of the source message ci combined with the corresponding parity check bits cp for that source message ci. The encodings c are transmitted, with the receiving network element receiving a signal vector r=c+n, n being the noise added by the channel. Because the decoder at the receiver also knows matrix H, it can compute a vector z=Hr. However, because r=c+n, and because Hc=0:z=Hr=Hc+Hn=Hn  (2)The decoding process thus involves finding the most sparse vector x that satisfies:Hx=z  (3)over GF(2). This vector x becomes the best guess for noise vector n, which can be subtracted from the received signal vector r to recover encodings c, from which the original source message ci is recoverable.
There are many known implementations of LDPC codes. Some of these LDPC codes have been described as providing code performance that approaches the Shannon limit, as described in MacKay et al., “Comparison of Constructions of Irregular Gallager Codes”, Trans. Comm., Vol. 47, No. 10 (IEEE, October 1999), pp. 1449-54, and in Tanner et al., “A Class of Group-Structured LDPC Codes”, ISTCA-2001 Proc. (Ambleside, England, 2001).
In theory, the encoding of data words according to an LDPC code is straightforward. Given enough memory or small enough data words, one can store all possible code words in a lookup table, and look up the code word in the table according to the data word to be transmitted. But modern data words to be encoded are on the order of 1 kbits and larger, rendering lookup tables prohibitively large and cumbersome. Accordingly, algorithms have been developed that derive codewords, in real time, from the data words to be transmitted. A straightforward approach for generating a codeword is to consider the n-bit codeword vector c in its systematic form, having a data or information portion ci and an m-bit parity portion cp such that c=(ci|cp). Similarly, parity matrix H is placed into a systematic form Hsys, preferably in a lower triangular form for the m parity bits. In this conventional encoder, the information portion ci is filled with n-m information bits, and the m parity bits are derived by back-substitution with the systematic parity matrix Hsys. This approach is described in Richardson and Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. on Information Theory, Vol. 47, No. 2 (February 2001), pp. 638-656. This article indicates that, through matrix manipulation, the encoding of LDPC codewords can be accomplished in a number of operations that approaches a linear relationship with the size n of the codewords. However, the computational efficiency in this and other conventional LDPC encoding techniques does not necessarily translate into an efficient encoder hardware architecture. Specifically, these and other conventional encoder architectures are inefficient because they typically involve the storing of inverse matrices, by way of which the parity check of equation (1), or a corollary, is solved in the encoding operation.
By way of further background, my copending patent application Ser. No. 10/329,597, filed Dec. 26, 2002, now published as U.S. Patent Publication No. US 2004/0034828, and my copending patent application Ser. No. 10/806,879, filed Mar. 23, 2004, and now published as U.S. Patent Publication No. US 2004/0194007 A1, both commonly assigned herewith and incorporated herein by this reference, describe a family of structured irregular LDPC codes, and decoding architectures for those codes. The quasi-cyclic structure of this family of LDPC codes can also provide efficiencies in the hardware implementation of the encoder, as described in my copending patent application Ser. No. 10/724,280, filed Nov. 28, 2003, now published as U.S. Patent Publication No. US 2004/0148560 A1, commonly assigned herewith and incorporated herein by this reference. The encoder and encoding method that are described in U.S. Patent Publication No. US 2004/0148560 A1 follow a generalized approach, and are capable of handling such complications as row rank deficiency.
By way of still further background, my copending patent application Ser. No. 11/201,391, filed Aug. 10, 2005, commonly assigned herewith and incorporated herein by this reference, describes constraints on this family of structured irregular LDPC codes that enable recursive, and efficient, encoding of communications.
By way of further background, as fundamental in the coding art, the “code rate” of a particular code is a unit of measure corresponding to the number of information bits contained within a code word. Specifically, as typically used in the art, the code rate is the ratio of the number of information bits within a transmitted code word to the total number of bits transmitted within the code word (i.e., information bits plus parity bits, for systematic codes). For example, a code rate of 1:2, or 1/2, refers to a code word in which one-half of its bits are information bits, and the other one-half of the bits are parity bits. A code rate of 2:3 thus has one-half as many parity bits as information bits. As such, the closer that the code rate approaches a 1:1 ratio, the higher the effective information data rate, all other parameters being equal. Uncoded transmissions are thus at a code rate of 1:1, because no parity bits are transmitted.
The use of “length-reduced” code words is known in the art. In general, a “length-reduced” code word involves eliminating bits of the code word, as transmitted, from the full length of the code word as encoded. One known approach for reducing the code word length is by way of “puncturing” of the code word. In this approach, certain bits of the code word are simply not transmitted in the code word. In decoding the transmitted punctured code word, the missing bits are reconstructed in the decoding process from the transmitted bits of the code word, as a result of the “correction” properties of the coding. The receiver, of course, must know which bits of the code word were punctured, in order to accurately retrieve the information. Puncturing may be constrained to the parity bits of the systematic code word; however, information bits may also be punctured if desired. In general, puncturing increases the code rate of the transmission, at a cost of code performance (i.e., higher error rate for a given SNR, or higher SNR being required for a given error rate).
Another approach for length reduction is referred to in the art as “shortening”. According to this approach, which is applied to systematic codes, a selected number of information bits is forced to a known state (e.g., “0”), and therefore need not be transmitted. A full complement of parity bits must be generated from the information bits including the forced-value bits, however, in order for the coding to be effective, and of course the receiver must be aware of which information bits are not transmitted (and their forced state, of course). The use of “shortening” techniques is useful in situations in which the code (and code word length) is constrained to a certain length, but in which the available transmission word length is shorter than the length of the information portion of the full code word, or in which the number of necessary information bits is less than that available for the code word. Code “shortening” results in a reduction in the overall code rate, however, considering that the same number of information bits and total bits are not transmitted in the shortened code word (in the code rate ratio, both the numerator and the denominator are reduced by the same absolute value). Shortening tends to improve the performance of the code, however, because there is less overall uncertainty in the full code word after shortening is reversed in the receiver (i.e., the state of the shortened bits is known with certainty).
By way of further background, many known communications standards specify particular coding approaches, including specific codes, and specific code word lengths. For example, the code set for the IEEE 802.16d/e standards for “WiMAX” and “WiBro” broadband wireless data communication technologies, specifies nineteen available code word lengths, each of which may be encoded at any of three code rates. Transmissions according to the standards may be carried out using any one of those code word lengths, at any of the three code rates. The decoding circuitry for receiving such communications must contemplate any of the nineteen code word lengths, at any of the three code rates, in order to fully meet the standard. In this example, therefore, fifty-seven codes must be contemplated in the decoder hardware.